The present invention is related to overflow prediction in arithmetic circuits that perform addition operations.
It is often necessary in high-speed arithmetic units to predict whether the addition of two floating point numbers will result in an overflow without actually doing the addition. The addition can be expensive, the cost increases with the width of the input operands. Use of redundant number systems like carry save format to perform addition keeps addition delay independent of input mantissa width, but makes it difficult to determine if the sum that is in carry-save format has overflowed. Some examples of applications of overflow prediction are floating point multiply-accumulate units and wave digital filters.
Traditional implementations of overflow detection during addition of two numbers in twos complement format checks the carry into and carry out of the most significant digit of the sum. However this method requires the addition to be done first. It is also not applicable to addition in redundant format because the final sum in this case is in carry and sum form. Other implementations of overflow detection require the use of an up/down counter between the circuit stage that detects overflow in a sum and the stage that corrects overflow in a sum. The counter is a necessary part of this implementation because it is needed to correct the final sum. Other prior art predicts overflow in redundant format addition by checking the most significant three bits of the carry and sum vectors and the sign bits of the input operands.
One use of the overflow detector of the present invention is in a FIR (finite impulse response) filter using a fast floating point multiply-accumulate (FMAC) unit, which multiplies input operands and accumulates them with the previous multiplication result. An FMAC unit is depicted in FIG. 1. In this implementation, the addition 46 is performed in carry-save format so that it can be performed quickly. The adder receives input operands 43 and 44 and transmits results in carry-save format. It is necessary to predict whether the result of the addition has overflowed so that compensation with a right shifter 47 can be performed before the mantissa sum is transmitted to an earlier stage of the multiplier-accumulator circuit. Since the result is in carry-save format, this is not trivial. It is especially difficult because carry-save format addition does not follow the rules of “normal” addition.
In the carry-save format, the carry term is shifted left by 1 bit position (equivalent to multiplying the carry value by 2) before addition is performed. If there is a negative carry term and a positive sum term, the left shift that is performed after carry save addition might shift out the leading one of the carry term, making it a positive number (the leading bit indicates sign). The addition of two seemingly positive numbers (sum and carry) may then produce a valid negative number. This seemingly contradictory result is valid in carry-save addition but invalidates the assumptions made in the designs of many LZAs (Leading Zero Anticipation circuits). For example, consider a carry (value −6) and a sum (value 7) with expected final result −6×2+7=−5. The corresponding 4 bit binary vectors in 2's complement are carry 1010 and sum 0111. When the carry is shifted left 1 bit, it becomes 0100. Adding 0100 (which is now seemingly a positive number) to 0111 (also a positive number) gives 1011 which is a negative number (−5) and is the correct expected final result.